//P1972
/*
离线算法实现，按r排序从前向后枚举
对第i个贝壳求出前一个和它相同的f[i]
区间[l,r]=[l,r-1]+1
g[i]记录前一个值为i的数在哪里，
f[i]=g[a[i]]
eg.
   1 2 5 2 3 3 5
f: 4 3 3 2 1 1 0
   4 3 3{3 2 2 1}
*/
for(int i=1;i<=n;++i)
{
	f[i]=g[a[i]];
		g[a[i]]=i;
		add(f[i]+1,1);	//处理f数组
		add(i+1,-1);	//区间[f[i]+1,i]增加
		for(;q[j].r==i&&j<=n;++j)
				q[j].ans=ask(q[j].l);//枚举询问
}
